package 每日一题;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-06-27
 **/

public class No773滑动谜题 {

    /**
     * 在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
     * 一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
     * 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
     * 给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
     *
     * 示例：
     * 输入：board = [[1,2,3],[4,0,5]]
     * 输出：1
     * 解释：交换 0 和 5 ，1 步完成
     * 输入：board = [[1,2,3],[5,4,0]]
     * 输出：-1
     * 解释：没有办法完成谜板
     * 输入：board = [[4,1,2],[5,0,3]]
     * 输出：5
     * 解释：
     * 最少完成谜板的最少移动次数是 5 ，
     * 一种移动路径:
     * 尚未移动: [[4,1,2],[5,0,3]]
     * 移动 1 次: [[4,1,2],[0,5,3]]
     * 移动 2 次: [[0,1,2],[4,5,3]]
     * 移动 3 次: [[1,0,2],[4,5,3]]
     * 移动 4 次: [[1,2,0],[4,5,3]]
     * 移动 5 次: [[1,2,3],[4,5,0]]
     * 输入：board = [[3,2,4],[1,5,0]]
     * 输出：14
     * 提示：
     * board 是一个如上所述的 2 x 3 的数组.
     * board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.
     *
     * 对0进行移动。
     */

    private Set<String> set=new HashSet<>();
    private String target="123450";
    /**
     * 当前下标周围的下标
     */
    private int[][] aroundIndex=new int[][]{{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};

    public int slidingPuzzle(int[][] board) {


        StringBuilder sb=new StringBuilder();
        for (int[] ints : board) {
            for (int anInt : ints) {
                sb.append(anInt);
            }
        }

        String sourceStr = sb.toString();

        if(sourceStr.equals(target)){
            return 0;
        }

        Set<String> set=new HashSet<>();
        Deque<String> queue=new ArrayDeque<>();
        queue.addLast(sourceStr);
        set.add(sourceStr);
        int deep=0;

        while (!queue.isEmpty()){

            int count=queue.size();
            deep++;

            while (count>0){

                String str = queue.removeFirst();
                count--;

                //只对0的下标进行移动,不是对所有下标进行移动
                int i=str.indexOf('0');
                for (int j = 0; j < aroundIndex[i].length; j++) {
                    String s = this.exchangeChar(str, i, aroundIndex[i][j]);
                    if(s.equals(target)){
                        return deep;
                    }
                    if(!set.contains(s)){
                        set.add(s);
                        queue.addLast(s);
                    }
                }

            }

        }

        return -1;
    }

    private String exchangeChar(String str,int index1,int index2) {
        char[] chars = str.toCharArray();
        char c=chars[index1];
        chars[index1]=chars[index2];
        chars[index2]=c;
        return new String(chars);
    }

    public static void main(String[] args) {
        No773滑动谜题 n=new No773滑动谜题();
        int[][] arr=new int[][]{{3,2,4},{1,5,0}};
        int result = n.slidingPuzzle(arr);
        System.out.println(result);
    }

}
